// 哈希表-链地址法实现

function HashTable() {
  // 属性
  this.storage = [] // 元素存储的的数组
  this.count = 0 // 用于统计填充因子，作扩容
  this.limit = 7 // 当前总长度

  // 方法
  // 哈希函数
  HashTable.prototype.hashFunc = function (str, size) {
    // 1、定义hashCode变量
    var hashCode = 0
    // 2、霍纳算法，计算hashCode的值
    for (var i = 0; i < str.length; i++) {
      // 获取当前的Unicode编码，常用哈希质数是37
      hashCode = 37 * hashCode + str.charCodeAt(i)
    }
    // 取余操作
    var index = hashCode % size
    return index
  }
  // 插入和修改操作
  HashTable.prototype.put = function (key, value) {
    // 1、根据key获取index
    var index = this.hashFunc(key, this.limit)
    // 2、根据index取出对应的bucket
    var bucket = this.storage[index]
    // 3、判断该bucket是否为null
    if (bucket == null) {
      bucket = []
      this.storage[index] = bucket
    }
    // 4、判断该是否是修改数据
    for (var i = 0; i < bucket.length; i++) {
      var tuple = bucket[i]
      if (tuple[0] == key) {
        // 若匹配到，则修改该数据的数据值，然后直接返回
        tuple[1] = value
        return
      }
    }
    // 5、进行添加操作
    bucket.push([key, value])
    this.count += 1
    // 6、判断是否需要扩容操作，自动扩容
    if (this.count > this.limit * 0.75) {
      // this.resize(this.limit * 2) // 扩容两倍
      var newSize = this.limit * 2
      var newPrime = this.getPrime(newSize)
      this.resize(newPrime)
    }
  }

  // 获取方法
  HashTable.prototype.get = function (key) {
    // 1、根据key获取index
    var index = this.hashFunc(key, this.limit)
    // 2、获取index对应的bucket
    var bucket = this.storage[index]
    // 3、判断bucket是否为null
    if (bucket == null) {
      return null
    }
    // 4、有bucket，那么就进行线性查找
    for (var i = 0; i < bucket.length; i++) {
      var tuple = bucket[i]
      if (tuple[0] == key) {
        return tuple[1]
      }
    }
    // 5、依然没有找到，则返回null
    return null
  }

  // 删除操作
  HashTable.prototype.remove = function (key) {
    // 1、根据key获取index
    var index = this.hashFunc(key, this.limit)

    // 2、获取index对应的bucket
    var bucket = this.storage[index]
    // 3、判断bucket是否存在，若不存在，则返回null
    if (bucket == null) {
      return null
    }
    // 4、有bucket，那么就进行线性查找，然后删除
    for (var i = 0; i < bucket.length; i++) {
      var tuple = bucket[i]
      if (tuple[0] == key) {
        bucket.splice(i, 1)
        this.count -= 1
        // 到一定程度，则缩小容量
        if (this.limit > 7 && this.count < this.limit * 0.25) {
          // this.resize(Math.floor(this.limit / 2))
          var newSize = Math.floor(this.limit / 2)
          var newPrime = this.getPrime(newSize)
          this.resize(newPrime)
        }
        return tuple[1]
      }
    }
    // 5、依然没有找到，则返回null
    return null
  }

  // 其他方法
  // 判断哈希表是否为空
  HashTable.prototype.isEmpty = function () {
    return this.count == 0
  }
  // 获取哈希表元素个数
  HashTable.prototype.size = function () {
    return this.count
  }

  // *********************************************************
  // 哈希表的扩容/缩容
  HashTable.prototype.resize = function (newLimit) {
    // 1、保存旧的数组内容
    var oldStorage = this.storage
    // 2、重置所有的属性
    this.storage = []
    this.count = 0
    this.limit = newLimit
    // 3、遍历OldSmobile中所有的bucket
    for (var i = 0; i < oldStorage.length; i++) {
      // 3.1、取出对应的bucket
      var bucket = oldStorage[i]
      // 3.2、判断bucket是否为null
      if (bucket == null) {
        continue
      }
      // 3.3、如果bucket中有数据，则取出数据，重新插入
      for (var j = 0; j < bucket.length; j++) {
        var tuple = bucket[j]
        // 重新插入
        this.put(tuple[0], tuple[0])
      }
    }
  }

  // 判断某个数字是否为质数
  HashTable.prototype.isPrime = function (num) {
    var temp = parseInt(Math.sqrt(num))
    for (var i = 2; i <= temp; i++) {
      if (num % i === 0) {
        return false
      }
    }
    return true
  }

  // 获取质数的方法

  HashTable.prototype.getPrime = function (num) {
    while (!this.isPrime(num)) {
      num++
    }
    return num
  }
}

// 测试哈希表
var ht = new HashTable()

// 插入数据
ht.put('abc', '123')
ht.put('cba', '321')
ht.put('nba', '521')
ht.put('mba', '520')

console.log(ht.get('abc'))
console.log(ht.put('abc', 111))
console.log(ht.get('abc'))

console.log(ht.remove('abc'))
console.log(ht.get('abc'))
